package leetcode.editor.cn;

public class P409LongestPalindrome {
    public static void main(String[] args) {
        Solution solution = new P409LongestPalindrome().new Solution();
        System.out.println(solution.longestPalindrome("abccccdd"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int longestPalindrome(String s) {
            int length = s.length();
            boolean[][] visited = new boolean[length][length];
            int max = 0;
            for (int j = 0; j < length; j++) {
                for (int i = 0; i <= j; i++) {
                    visited[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 2 || visited[i + 1][j - 1]);
                    if (visited[i][j]) {
                        if (j - i + 1 > max) {
                            max = j + 1 - i;
                        }
                    }
                }
            }
            return max;
        }


        public int longestPalindromeMy(String s) {
            int length = s.length();
            int max = 0;
            for (int i = 0; i < length; i++) {
                for (int j = length - 1; j > i; j--) {
                    if (valid(s, i, j)) {
                        max = Math.max(max, j - i + 1);
                    }
                }
            }
            return max;
        }

        public boolean valid(String s, int left, int right) {
            while (left < right) {
                if (s.charAt(left++) != s.charAt(right--)) {
                    return false;
                }
            }
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}